package LeetCode;

/**
 * @Author Kechelle
 * @Date 2020/9/16 9:34
 * @Version 1.0
 */
public class Code69 {
    public static int mySqrt(int x) {
        if (x<=1) return x;
        long left = 0;
        long right = x;
        while (left<=right){
            long mid = (left + right)/2;
            if (mid * mid == x){
                return (int) mid;
            }else if (mid * mid < x){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return (int) right;
    }

    public static void main(String[] args) {
        System.out.println(Code69.mySqrt(4));
    }
}

/*
if (x<=1) return x;
        long i = 0;
        long res = 0;
        while (res<=x){
            i++;
            res = i*i;
        }
        return (int) (i-1);
 */
